package utils;

/**
 * 最小二叉堆
 * @author 车宗绍 Che Zongshao
 * @date 2014/12/31
 */

public class BinaryHeap {

	private int currentSize;		// 当前最小二叉堆的size
	private Node[] array;			// 最小二叉堆 由数组实现
	
	/**
	 * 下滤操作
	 * @param hole
	 */
	private void percolateDown(int hole) {
		int child;
		Node tmp = array[hole];
		
		for (; hole*2 <= currentSize; hole = child) {
			child = hole * 2;
			if (child != currentSize && array[child+1].getFn() < array[child].getFn()) {
				// 如果右边节点的值小于左边节点的值，child指向右边
				child++;
			}
			if (array[child].getFn() < tmp.getFn()) {
				// 如果child的值小于tmp的值，下滤
				array[hole] = array[child];
			} else {
				break;
			}
		}
		array[hole] = tmp;
	}
	
	/**
	 * 构建Heap
	 */
	private void buildHeap() {
		for (int i = currentSize / 2; i > 0; i--) {
			percolateDown(i);
		}
	}
	
	/**
	 * 扩展array数组
	 * @param newSize
	 */
	private void enlargeArray(int newSize) {
		Node[] oldArr = array;  
        Node[] newArr = new Node[newSize];  
        for (int i = 1; i < array.length; i++)  
            newArr[i] = oldArr[i];  
        array = newArr;
	}
	
	public BinaryHeap() {
		currentSize = 0;
		array = new Node[2];
	}
	public BinaryHeap(Node[] nodes) {
		currentSize = nodes.length;
		array = new Node[(currentSize + 2) * 11 / 10];
		int i = 1;
		for (Node item : nodes) {
			array[i++] = item;
		}
		buildHeap();
	}
	
	/**
	 * 插入Node
	 * @param x
	 */
	public void insert(Node x) {
		if (currentSize == array.length - 1) {
			enlargeArray(array.length * 2 + 1);
		}
		// 上滤Percolate up
		int hole = ++currentSize;
		for (; hole > 1 && x.getFn() < array[hole/2].getFn(); hole /= 2) {
			array[hole] = array[hole/2];
		}
		array[hole] = x;
	}
	
	/**
	 * 找到最小f(n)的Node
	 * @return minItem: 最小f(n)的Node; null: 堆是空的时
	 */
	public Node findMin() {
		if (isEmpty()) {
			return null;
		} else {
			return array[1];
		}
	}
	
	/**
	 * 删除最小f(n)的Node
	 * @return minItem: 最小f(n)的Node; null: 堆是空的时
	 */
	public Node deleteMin() {
		if (isEmpty()) {
			return null;
		}
		Node minItem = findMin();
		if (currentSize > 1) {
			array[1] = array[currentSize--];
			// 下滤
			percolateDown(1);
		} else {
			currentSize = 0;
			array[1] = null;
		}
		
		return minItem;
	}
	
	/**
	 * 堆是空的吗？
	 * @return true: 空的; false: 非空
	 */
	public boolean isEmpty() {
		if (currentSize <= 0) {
			return true;
		} else {
			return false;
		}
	}
	public void makeEmpty() {
		
	}
}